package cn.datastruct.six;
/*
*  二分查找思路：
*       1、如果大于中间值则向右递归
*       2、如果小于中间值则向左递归
*       3、如果等于中间值则返回下标
*       4、如果没有找到则返回-1
*       5、查找多个值，可二分查找找到后左右顺序查找
* */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 19, 23, 35, 235};
        System.out.println(binarySearch(arr, 0, arr.length - 1, 9));
    }

    /**
     * @param value 待查找的值
     * @param arr 查找的数组
     * @param left 左边的下标
     * @param right 右边的下标
     * @return
     */
    public static int binarySearch(int[] arr, int left, int right, int value){
        if(left > right || value < arr[left] || value > arr[right])//如果没有找到，递归退出的条件
            return -1;
//        int mid = (left + right) / 2;//the number of middle
        int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);//the number of middle,InsertValueSearch
        int midval = arr[mid];//the  value of arr middle
        if(value > midval){//如果大于中间值则向右递归
            return binarySearch(arr, mid + 1, right, value);
        }else if(value < midval){//如果小于中间值则向左递归
            return binarySearch(arr, left, mid - 1, value);
        }else {//如果等于中间值则返回下标
            return mid;
        }
    }
}
